﻿package{
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.events.MouseEvent;
	import flash.events.KeyboardEvent;
	import Box2D.Dynamics.*;
	import Box2D.Collision.*;
	import Box2D.Collision.Shapes.*;
	import Box2D.Common.Math.*;
	import Box2D.Dynamics.Joints.*;
	import flash.display.MovieClip;
	import flash.display.Stage;
	import flash.display.DisplayObject;
	import flash.text.TextField;
	import flash.ui.GameInput;
	import Box2D.Dynamics.Contacts.b2ContactEdge;
	import flash.utils.Dictionary;

	public class absolute extends Sprite {
		
		public var world:b2World=new b2World(new b2Vec2(0,10.0),true);
		public var offline_world:b2World=new b2World(new b2Vec2(0,10.0),true);
		public var world_scale:int=30;
		public var previousX:int=-1;
		public var previousY:int=-1;
		public var imDrawing:Boolean=false;
		public var imFirst:Boolean=true;
		public var circleStart:b2Vec2;
		public var currentCircle:b2Body;
		public var offlineCircle:b2Body;
		var playBtn:b2Body;
		var playBtnText:TextField;
		public var scrollDifferenceX:int;
		public var scrollDifferenceY:int;
		public var stepScrollDifferenceX:Number;
		public var stepScrollDifferenceY:Number;
		public var previousStepCircleX:Number;
		public var previousStepCircleY:Number;
		public var playMode:Boolean;
		public var edgeList:Array;
		public var currentGameState:gamestate;
		public var maxEvaluationValue:Number;
		//public var firstEvaluationValue:Number;
		//public var allTheSame:Boolean;
		public var nodes:Array;
		public var goalReached:Boolean;
		public var goodHalfOfPyramid:Array;
		public var bestNode:int;
		public var queue:Array;
		public var stepsSinceStart:int;
		public var searchyMcDeperthson:int;
		
		public var actionableArray:Array = new Array();
		public var actionArray:Array = new Array();
		public var actionStep:Number = 10;
		public var mySearch:Boolean = true;
		public function absolute():void {
			debug_draw();
			/*
			draw_box(250,300,500,100,false);
			draw_circle(375,100,50,true);
			draw_triangle(400, 200, 50, 50, true);
			draw_edge(50, 50, 100, 100, false);
			*/
			/*playBtn = draw_box(17, 10, 100, 30, false);
			playBtn.SetAwake(false);
			playBtn.SetActive(false);
			playBtnText = new TextField();
			playBtnText.border = true;
			playBtnText.x = -33;
			playBtnText.y = -6;
			playBtnText.text = "Play the game!";
			playBtnText.textColor = 0x000000;
			playBtnText.height = 31;
			playBtnText.width = 100;*/
			playMode = false;
			edgeList = new Array();
			//addChild(playBtnText);
			addEventListener(Event.ENTER_FRAME, update);
			stage.addEventListener(MouseEvent.MOUSE_DOWN, mouse_down_handler);
			stage.addEventListener(MouseEvent.MOUSE_MOVE, mouse_move_handler);
			stage.addEventListener(MouseEvent.MOUSE_UP, mouse_up_handler);
			stage.addEventListener(KeyboardEvent.KEY_DOWN, key_down_handler);
		}
		public function draw_circle(world:b2World,px,py,r,d):b2Body {
			var my_body:b2BodyDef= new b2BodyDef();
			my_body.position.Set(px, py);
			if (d) {
				my_body.type=b2Body.b2_dynamicBody;
			}
			var my_circle:b2CircleShape=new b2CircleShape(r/world_scale);
			var my_fixture:b2FixtureDef = new b2FixtureDef();
			my_fixture.shape=my_circle;
			my_fixture.density = 1;
			var world_body:b2Body=world.CreateBody(my_body);
			world_body.CreateFixture(my_fixture);
			return world_body;
		}
		public function draw_box(px,py,w,h,d):b2Body {
			var my_body:b2BodyDef= new b2BodyDef();
			my_body.position.Set(px/world_scale, py/world_scale);
			if (d) {
				my_body.type=b2Body.b2_dynamicBody;
			}
			var my_box:b2PolygonShape = new b2PolygonShape();
			my_box.SetAsBox(w/2/world_scale, h/2/world_scale);
			var my_fixture:b2FixtureDef = new b2FixtureDef();
			my_fixture.shape=my_box;
			var world_body:b2Body=world.CreateBody(my_body);
			world_body.CreateFixture(my_fixture);
			return world_body;
		}
		public function draw_triangle(px, py, w, h, d):void {
			var my_body:b2BodyDef= new b2BodyDef();
			var my_triangle:b2PolygonShape = new b2PolygonShape();
			var vertex1:b2Vec2 = new b2Vec2(0, (-h + 1)/world_scale);
			var vertex2:b2Vec2 = new b2Vec2((w)/world_scale, 1);
			var vertex3:b2Vec2 = new b2Vec2((-w)/world_scale, 1);
			var vertex_array:Array = [vertex1, vertex2, vertex3];
			my_triangle.SetAsArray(vertex_array, 3);
			my_body.position.Set(px/world_scale, py/world_scale);
			my_body.angle = 0;
			if (d) {
				my_body.type=b2Body.b2_dynamicBody;
			}
			var body:b2Body = world.CreateBody(my_body);
			var my_fixture:b2FixtureDef = new b2FixtureDef();
			my_fixture.shape = my_triangle;
			body.CreateFixture(my_fixture);
		}
		public function draw_edge(world:b2World, pstartx, pstarty, pendx, pendy, d):edge {
			var my_body:b2BodyDef = new b2BodyDef();
			var my_edge:b2PolygonShape = new b2PolygonShape();
			var start:b2Vec2 = new b2Vec2(pstartx/world_scale, pstarty/world_scale);
			var end:b2Vec2 = new b2Vec2(pendx/world_scale, pendy/world_scale);
			//var start:b2Vec2 = new b2Vec2(pstartx, pstarty);
			//var end:b2Vec2 = new b2Vec2(pendx, pendy);
			my_edge.SetAsEdge(start, end);
			//my_body.position.Set(((pstartx+pendx)/120)/world_scale, ((pstarty + pendy)/120)/world_scale);
			my_body.position.Set(0, 0);
			my_body.angle = 0;
			if (d) {
				my_body.type=b2Body.b2_dynamicBody;
			}
			var body:b2Body = world.CreateBody(my_body);
			var my_fixture:b2FixtureDef = new b2FixtureDef();
			my_fixture.shape = my_edge;
			my_fixture.friction = 1000;
			body.CreateFixture(my_fixture);
			var vectorArray:Array = new Array();
			vectorArray = [start, end];
			return new edge(vectorArray);
		}
		public function debug_draw():void {
			var debug_draw:b2DebugDraw = new b2DebugDraw();
			var debug_sprite:Sprite = new Sprite();
			addChild(debug_sprite);
			debug_draw.SetSprite(debug_sprite);
			debug_draw.SetDrawScale(world_scale);
			debug_draw.SetFlags(b2DebugDraw.e_shapeBit);
			world.SetDebugDraw(debug_draw);
		}
		public function update(e : Event):void {
			/*if (currentCircle != null && offlineCircle != null) {
				apply_torque_clockwise(currentCircle);
				set_offline_world(offlineEdgeList, currentCircle.GetPosition(), currentCircle.GetAngularVelocity(), currentCircle.GetLinearVelocity());
			}
			*/
			if (!playMode) {
				world.Step(1/30,10,10);
				world.ClearForces();
				world.DrawDebugData();
			}
			/*
			if (currentCircle != null && offlineCircle != null) {
				step_offline_world(true, 1);
				trace("CurrentX: " + currentCircle.GetPosition().x);
				trace("OfflineX: " + offlineCircle.GetPosition().x);
				trace("DifferenceX: " + (offlineCircle.GetPosition().x - currentCircle.GetPosition().x));
				trace("DifferenceY: " + (offlineCircle.GetPosition().y - currentCircle.GetPosition().y));
				trace("CurrentY: " + currentCircle.GetPosition().y);
				trace("OfflineY: " + offlineCircle.GetPosition().y);
				trace("CurrentAngVel: " + currentCircle.GetAngularVelocity());
				trace("OfflineAngVel: " + offlineCircle.GetAngularVelocity());
			}*/
			else {
				if (mySearch) {
				
					if (actionStep == searchyMcDeperthson || actionStep >= actionArray.length) {
						//trace("start search");
						this.actionArray = new Array();
						this.actionableArray = new Array();
						actionableArray = actionableArray.concat((search(new node(currentGameState, 10, true), searchyMcDeperthson)));
						for (i = 1; i < actionableArray.length; i++) {
							actionArray.push((actionableArray[i] as node).getActionTaken());
						}
						//trace("end search");
						//trace(currentGameState);
						var traceNode:node;
						if (actionableArray.length > 0) {
							traceNode = actionableArray[0] as node;
							//trace(traceNode.gameState.gameCircle.GetPosition().x);
							//trace(traceNode.gameState.gameCircle.GetPosition().y);
						}
						actionStep = 0;
					} 
				} 
				else {
					
				
				//trace("Stat: " + stat);
					var i:int;
					var stat = 5;
					if (stat == 0) {
						for (i = 0; i < 6; i++) {
							world.Step(1/30,10,10);
							world.ClearForces();
							world.DrawDebugData();
							stepsSinceStart++;
						}
					}
					else if (stat == 1) {
						for (i = 0; i < 6; i++) {
							apply_torque_counter_clockwise(currentCircle);
							world.Step(1/30,10,10);
							world.ClearForces();
							world.DrawDebugData();
							stepsSinceStart++;
						}
					}
					else if (stat == 2) {
						for (i = 0; i < 6; i++) {
							apply_torque_clockwise(currentCircle);
							world.Step(1/30,10,10);
							world.ClearForces();
							world.DrawDebugData();
							stepsSinceStart++;
						}
					}
				}
				
				//trace("ACTION ARRAY LENGTH IS");
				//trace(this.actionArray.length);
				/*for (i = 0; i < 6; i++) {
					world.Step(1/30,10,10);
					world.ClearForces();
					world.DrawDebugData();
				}*/
				//for (i = 0; i < edgeList.length; i++) {
					//trace((edgeList[i] as edge).hasBeenTouched());
				//}
				//scroll_with_ball();
				var actionToTake:Number = this.actionArray[actionStep];
				for (i = 0; i < 15; i++) {
					if (actionToTake == 1) {
						apply_torque_counter_clockwise(currentCircle);
					}
					if (actionToTake == 2) {
						apply_torque_clockwise(currentCircle);
					}
					world.Step(1/30,10,10);
					world.ClearForces();
					world.DrawDebugData();
				}
				actionStep++;
				currentGameState = new gamestate(currentCircle, edgeList, stepsSinceStart, circleStart);
				
				/*
				var contactEdge:b2ContactEdge = currentCircle.GetContactList();
				var currentEdge:edge;
				while (contactEdge != null) {
					var currentBody:b2Body;
					var shape:b2PolygonShape;
					var vertexVector:Vector.<b2Vec2>;
					var vertexArray:Array;
					var i:uint;
					var vertex:b2Vec2;
					
					if (contactEdge.contact.GetFixtureA().GetBody().GetPosition().x ==
					    currentCircle.GetPosition().x && 
						contactEdge.contact.GetFixtureA().GetBody().GetPosition().y ==
						currentCircle.GetPosition().y) {
							if (contactEdge.contact.GetFixtureB().GetBody().GetPosition().y <
								currentCircle.GetPosition().y) {
									currentBody = contactEdge.contact.GetFixtureB().GetBody();
									shape = currentBody.GetFixtureList().GetShape() as b2PolygonShape;
									vertexVector = shape.GetVertices();
									vertexArray = new Array();
									for (i = 0; i < vertexVector.length; i++) {
										vertex = vertexVector[i];
										vertexArray.push(vertex);
									}
									currentEdge = new edge(vertexArray, true);
									break;
							}
					} else {
						if (contactEdge.contact.GetFixtureA().GetBody().GetPosition().y < 
							currentCircle.GetPosition().y) {
								currentBody = contactEdge.contact.GetFixtureA().GetBody();
								shape = currentBody.GetFixtureList().GetShape() as b2PolygonShape;
								vertexVector = shape.GetVertices();
								vertexArray = new Array();
								for (i = 0; i < vertexVector.length; i++) {
									vertex = vertexVector[i];
									vertexArray.push(vertex);
								}
								currentEdge = new edge(vertexArray, true);
								break;
						}
					}
					contactEdge = contactEdge.next;
				}
				if (currentEdge != null) {
					currentGameState.setCurrentEdge(currentEdge);
				} else {
					currentGameState.setCurrentEdge(null);
				}
				*/
			}
		}
		public function mouse_down_handler(e : MouseEvent):void {
			previousX = mouseX;
			previousY = mouseY;
			imDrawing = true;
			if (imFirst) {
				circleStart = new b2Vec2((mouseX + 60)/world_scale, (mouseY - 60)/world_scale);
				scrollDifferenceX = 0;
				scrollDifferenceY = 0;
			}
			playMode = false;
		}
		public function mouse_move_handler(e : MouseEvent):void {
			if (imDrawing) {
				var newBody_edge:edge = draw_edge(world, previousX, previousY, mouseX, mouseY, false);
				edgeList.push(draw_edge(offline_world, previousX, previousY, mouseX, mouseY, false));
				//for (var i:uint; i < edgeList.length; i++) {
				//	trace(edgeList[i].toString());
				//}
			}
			previousX= mouseX;
			previousY= mouseY;
		}
		public function mouse_up_handler(e : MouseEvent):void {
			/*if (mouseX <= playBtnText.x + 100 && 
				mouseX >= playBtnText.x &&
				mouseY <= playBtnText.y + 31 &&
				mouseY >= playBtnText.y) {
					play_button_listener(e);
			}*/
			imDrawing = false;
			imFirst = false;
		}
		public function key_down_handler(e : KeyboardEvent):void {
			if (e.keyCode == 38) {
				scroll_up(8);
			}
			else if (e.keyCode == 40) {
				scroll_up(-8);
			}
			else if (e.keyCode == 37) {
				scroll_left(8);
			}
			else if (e.keyCode == 39) {
				scroll_left(-8);
			}
			//SpaceBar
			else if (e.keyCode == 32) {
				//apply_torque_clockwise(currentCircle);
			}
			//Shift
			else if (e.keyCode == 16) {
				//apply_torque_counter_clockwise(currentCircle);
			}
			else if (e.keyCode == 80) {
				play_button_listener();
			}
		}
		public function scroll_up(pixels:Number):void {
			for(var i:int = 0; i < stage.numChildren; i++){
                stage.getChildAt(i).y += pixels;
			}
			/*playBtn.GetPosition().y -= pixels/world_scale;
			playBtnText.y -= pixels;*/
			scrollDifferenceY += pixels;
		}
		public function scroll_left(pixels:Number):void {
			for(var i:int = 0; i < stage.numChildren; i++){
                stage.getChildAt(i).x += pixels;
			}
			/*playBtn.GetPosition().x -= pixels/world_scale;
			playBtnText.x -= pixels;*/
			scrollDifferenceX += pixels;
		}
		public function apply_torque_clockwise(circle:b2Body):void {
			if (circle.GetAngularVelocity() < 20.0) {
				circle.ApplyTorque(20 * circle.GetMass());
			}
		}
		public function apply_torque_counter_clockwise(circle:b2Body):void {
			if (circle.GetAngularVelocity() > -20.0) {
				circle.ApplyTorque(-20 * circle.GetMass());
			}
		}
		public function play_button_listener():void {
			if (currentCircle != null) {
				world.DestroyBody(currentCircle);
			}
			goalReached = false;
			scroll_to_start();
			playMode = true;
			currentCircle = draw_circle(world, circleStart.x, circleStart.y, 20, true);
			//set_offline_world(new gamestate(currentCircle, edgeList, 0, circleStart));
			previousStepCircleX = currentCircle.GetPosition().x;
			previousStepCircleY = currentCircle.GetPosition().y;
			stepsSinceStart = 0;
			for (var i = 0; i < edgeList.length; i++) {
				(edgeList[i] as edge).setTimesTouched(0);
			}
			searchyMcDeperthson = Math.ceil(3000 / edgeList.length);
			this.actionStep = searchyMcDeperthson;
			currentGameState = new gamestate(currentCircle, edgeList, stepsSinceStart, circleStart);
		}
		public function scroll_to_start():void {
			scroll_up(-scrollDifferenceY);
			scroll_left(-scrollDifferenceX);
			scrollDifferenceX = 0;
			scrollDifferenceY = 0;
		}
		public function scroll_with_ball():void {
			stepScrollDifferenceX = currentCircle.GetPosition().x - previousStepCircleX;
			stepScrollDifferenceY = currentCircle.GetPosition().y - previousStepCircleY;
			previousStepCircleX = currentCircle.GetPosition().x;
			previousStepCircleY = currentCircle.GetPosition().y;
			scroll_up(-stepScrollDifferenceY * world_scale);
			scroll_left(-stepScrollDifferenceX * world_scale);
		}
		public function set_and_step_offline_world(inputState:gamestate, isTorqueClockwise:Boolean, numSteps:int):gamestate {
			var outputEdgeList:Array = new Array();
			outputEdgeList = outputEdgeList.concat(inputState.getEdgeList());
			if (offlineCircle != null) {
				offline_world.DestroyBody(offlineCircle);
			}
			offlineCircle = draw_circle(offline_world, inputState.getPositionX(), inputState.getPositionY(), 20, true);
			offlineCircle.SetAngularVelocity(inputState.getAngularVelocity());
			offlineCircle.SetLinearVelocity(inputState.getLinearVelocity());
			for (var i:int = 0; i < numSteps; i++) {
				if (isTorqueClockwise) {
					apply_torque_clockwise(offlineCircle);
				}
				else {
					apply_torque_counter_clockwise(offlineCircle);
				}
				offline_world.Step(1/30, 10, 10);
				offline_world.ClearForces();
				//check for touches and update edgeList
				var contactEdge:b2ContactEdge = offlineCircle.GetContactList();
				//trace("Here4");
				//trace(contactEdge)
				//trace(currentCircle.GetContactList());
				while (contactEdge != null) {
					//trace("Here3");
					var currentBody:b2Body;
					var shape:b2PolygonShape;
					var vertexVector:Vector.<b2Vec2>;
					var vertexArray:Array;
					var j:uint;
					var vertex:b2Vec2;
					var currentEdge:edge;
					
					if (contactEdge.contact.GetFixtureA().GetBody().GetPosition().x ==
					    offlineCircle.GetPosition().x && 
						contactEdge.contact.GetFixtureA().GetBody().GetPosition().y ==
						offlineCircle.GetPosition().y) {
						currentBody = contactEdge.contact.GetFixtureB().GetBody();
					} else {
						currentBody = contactEdge.contact.GetFixtureA().GetBody();
					}
					shape = currentBody.GetFixtureList().GetShape() as b2PolygonShape;
					vertexVector = shape.GetVertices();
					vertexArray = new Array();
					for (j = 0; j < vertexVector.length; j++) {
						vertex = vertexVector[j];
						vertexArray.push(vertex);
					}
					currentEdge = new edge(vertexArray, 1);
					//trace("Here2");
					//outputEdgeList = inputState.getEdgeList();
					for (var k = 0; k < outputEdgeList.length; k++) {
						var searchEdge:edge = outputEdgeList[k] as edge;
						if (currentEdge.edgeStart.x == searchEdge.edgeStart.x &&
							currentEdge.edgeStart.y == searchEdge.edgeStart.y &&
							currentEdge.edgeEnd.x == searchEdge.edgeEnd.x &&
							currentEdge.edgeEnd.y == searchEdge.edgeEnd.y) {
								//trace("Here");
								//(outputEdgeList[k] as edge).incrementTimesTouched();
								/*if (k - 3 >= 0 && k + 3 < outputEdgeList.length) {
									for (var m = 0; m <= 6; m++) {
										//if ((outputEdgeList[k - 10 + m] as edge).getTimesTouched() == 0) {
											(outputEdgeList[k - 3 + m] as edge).incrementTimesTouched();
										//}
									}
								}*/
								//else {
									(outputEdgeList[k] as edge).incrementTimesTouched();
								//}
						}
						else {
							//outputEdgeList.push(searchEdge);
						}
					}
					contactEdge = contactEdge.next;
				}
			}
			return new gamestate(offlineCircle, outputEdgeList, inputState.getStepsSinceStart()+numSteps, circleStart);
		}
		public function search(rootNode:node, searchDepth:int):Array {
			//trace("initializing");
			var closedSet:Array = new Array();
			var openSet:Array = new Array();
			openSet.push(rootNode);
			var came_from:Dictionary = new Dictionary();
			
			var g_score:Dictionary = new Dictionary();
			var f_score:Dictionary = new Dictionary();
			
			g_score[rootNode] = 0;
			f_score[rootNode] = g_score[rootNode] + heuristic_cost(rootNode);
			var depth = 0;
			//trace("initialization complete");
			//trace("begin open set iteration");
			while(openSet.length > 0 && depth < searchDepth) {
				var current:node = null;
				//trace("pick best node");
				for (i = 0; i < openSet.length; i++) {
					if (current == null) {
						current = openSet[i] as node;
						continue;
					}
					if (f_score[current] > f_score[openSet[i]]) {
						current = openSet[i] as node;
					}
				}
				//trace("picked the best node");
				//trace("check for goal state");
				var foundGoalState:Boolean = false
				var edgesTouched = 0;
				for (i = 0; i < current.getGameState().getEdgeList().length; i++) {
					if ((current.getGameState().getEdgeList()[i] as edge).getTimesTouched() > 0) {
						edgesTouched++;
					}
				}
				if (edgesTouched == current.getGameState().getEdgeList().length) {
					foundGoalState = true;
				}
				if (foundGoalState) {
					//trace("goal state found");
					return reconstruct_path(came_from, current);
				}
				//trace("did not find goal state");
				//trace("remove currentNode from open set");
				for (i = 0; i < openSet.length; i++) {
					var testNode:node = openSet[i] as node;
					if (current.equals(testNode)) {
						openSet.splice(i, 1);
						break;
					}
				}
				//for (i = 0; i < openSet.length; i++) {
					//trace(openSet[i]);
				//}
				//var transitiveSet = new Array();
				//transitiveSet = transitiveSet.concat((openS));
				//openSet = new Array();
				//openSet = openSet.concat(transitiveSet);
				//for (i = 0; i < openSet.length; i++) {
					//trace(openSet[i]);
				//}
				closedSet.push(current);
				//trace("removal complete");
				//trace("generate neighbors");
				var neighborArray:Array = new Array();
				neighborArray = neighborArray.concat((generateNeighbors(current)));
				
				//trace("neighbors generated");
				//trace("begin iterating through neighbors");
				for (i = 0; i < neighborArray.length; i++) {
					var neighbor:node = neighborArray[i] as node;
					//trace(neighbor);
					var isClosed:Boolean = false;
					//trace("check if neighbor is closed");
					for (var j = 0; j < closedSet.length; j++) {
						if (neighbor.equals(closedSet[j] as node)) {
							isClosed = true;
						}
					}
					if (isClosed) {
						//trace("neighbor is closed");
						continue;
					}
					//trace("neighbor is not closed");
					//trace("check for neighbor in open set");
					var tentative_g_score:Number = g_score[current] + 1;
					var neighborInOpenSet = false;
					for (j = 0; j < openSet.length; j++) {
						testNode = openSet[j] as node;
						//trace(testNode);
						if (testNode.equals(neighbor)) {
							//trace("neighbor in open set");
							neighborInOpenSet = true;
						}
					}
					if (!neighborInOpenSet || (g_score[neighbor] != null && tentative_g_score < g_score[neighbor])) {
						//trace("neighbor not in open set");
						//trace("adding neigbor to open set");
						openSet.push(neighbor);
						came_from[neighbor] = current;
						g_score[neighbor] = tentative_g_score;
						f_score[neighbor] = g_score[neighbor] + heuristic_cost(neighbor);
					}
				}
				//trace("neighbor iteration complete");
				depth++;
			}
			//trace("open set iteration complete, or depth limit was reached");
			var bestNode:node = null;
			//trace("begin finding best node from what we have");
			for (var i = 0; i < openSet.length; i++) {
				var searchNode:node = openSet[i] as node;
				if (bestNode == null) {
					bestNode = openSet[0] as node;
					continue;
				}
				if (f_score[bestNode] > f_score[searchNode]) {
					bestNode = openSet[i] as node;
				}
			}
			//trace("finding best node complete");
			/*
			for (var i = 0; i < closedSet.length; i++) {
				var searchNode:node = closedSet[i] as node;
				if (bestNode == null) {
					bestNode = closedSet[0] as node;
					continue;
				}
				if (f_score[bestNode] > f_score[searchNode]) {
					bestNode = closedSet[i] as node;
				}
			}
			*/
			//trace("return from search");
			return reconstruct_path(came_from, bestNode);
			
			/*
			var toReturn:int = 0;
			maxEvaluationValue = 1;
			//firstEvaluationValue = 1;
			//allTheSame = true;
			var i:int;
			var j:int;
			if (goodHalfOfPyramid == null) {
				nodes = new Array();
				a_star_search_recursive(rootNode, searchDepth);
				//trace("Completed1");
				i = bestNode;
				while (i != 1 && i != 2 && i > 0) {
					i--;
					i = Math.floor(i / 2);
				}
				//trace("Completed3");
				toReturn = i;
				goodHalfOfPyramid = new Array();
				goodHalfOfPyramid[0] = nodes[i];
				for (i = 0; i < nodes.length; i++) {
					j = i;
					while (j > toReturn) {
						j--;
						j = Math.floor(j/2);
					}
					if (j == toReturn) {
						goodHalfOfPyramid.push(nodes[i]);
					}
				}
				//trace("Completed2");
			}
			else {
				if (!goalReached) {
					nodes = new Array();
					//expand_bottom_of_pyramid_and_traverse(rootNode, searchDepth, 0);
					a_star_search_recursive(rootNode, searchDepth);
					//trace("Completed4");
					i = bestNode;
					while (i != 1 && i != 2 && i > 0) {
						i--;
						i = Math.floor(i / 2);
					}
					toReturn = i;
					//trace(toReturn);
					goodHalfOfPyramid = new Array();
					goodHalfOfPyramid[0] = nodes[i];
					for (i = 0; i < nodes.length; i++) {
						j = i;
						while (j > toReturn) {
							j--;
							j = Math.floor(j/2);
						}
						if (j == toReturn) {
							goodHalfOfPyramid.push(nodes[i]);
						}
					}
				}
				else {
					toReturn = 3;
				}
			}
			//if (allTheSame) {
			//	toReturn = 4;
			//}
			return toReturn;
			*/
		}
		public function a_star_search_recursive(currentNode:node, searchDepth:int):void {
			nodes.push(currentNode);
			trace("Depth: " + searchDepth);
			if (currentNode.getGameState().getUntouchedEdges().length == 0) {
				goalReached = true;
			}
			if (maxEvaluationValue == 1) {
				maxEvaluationValue = currentNode.getEvaluation();
				//trace(maxEvaluationValue);
				bestNode = nodes.length - 1;
			}
			else {
				//trace(maxEvaluationValue);
				if (maxEvaluationValue < currentNode.getEvaluation()) {
					maxEvaluationValue = currentNode.getEvaluation();
					bestNode = nodes.length - 1;
				}
			}
			if (searchDepth == 0) {
				//trace(currentNode.getEvaluation());
				/*if (firstEvaluationValue == 1) {
					firstEvaluationValue = currentNode.getEvaluation();
				}
				else {
					if (firstEvaluationValue != currentNode.getEvaluation()) {
						allTheSame = false;
					}
				}*/
			}
			else {
				if (!goalReached) {
					a_star_search_recursive(new node(set_and_step_offline_world(currentNode.getGameState(), false, 6), searchDepth - 1), searchDepth - 1);
				}
				if (!goalReached) {
					a_star_search_recursive(new node(set_and_step_offline_world(currentNode.getGameState(), true, 6), searchDepth - 1), searchDepth - 1);
				}
			}
		}
		public function expand_bottom_of_pyramid_and_traverse(currentNode:node, searchDepth:int, goodPyramidIndex:int):void {
			currentNode.setDepth(searchDepth);
			nodes.push(currentNode);
			//trace(searchDepth);
			if (currentNode.getGameState().getUntouchedEdges().length == 0) {
				goalReached = true;
			}
			if (maxEvaluationValue == 1) {
				maxEvaluationValue = currentNode.getEvaluation();
				bestNode = nodes.length - 1;
			}
			else {
				if (maxEvaluationValue < currentNode.getEvaluation()) {
					maxEvaluationValue = currentNode.getEvaluation();
					bestNode = nodes.length - 1;
				}
			}
			if (searchDepth == 0) {
				/*if (firstEvaluationValue == 1) {
					firstEvaluationValue = currentNode.getEvaluation();
				}
				else {
					if (firstEvaluationValue != currentNode.getEvaluation()) {
						allTheSame = false;
					}
				}*/
			}
			else {
				if (searchDepth == 1) {
					//trace(currentNode.getEvaluation());
				}
				if (searchDepth == 1) {
					if (!goalReached) {
						expand_bottom_of_pyramid_and_traverse(new node(set_and_step_offline_world(currentNode.getGameState(), false, 6), searchDepth - 1), searchDepth - 1, -1);
					}
					if (!goalReached) {
						expand_bottom_of_pyramid_and_traverse(new node(set_and_step_offline_world(currentNode.getGameState(), true, 6), searchDepth - 1), searchDepth - 1, -1);
					}
				}
				else {
					expand_bottom_of_pyramid_and_traverse(goodHalfOfPyramid[goodPyramidIndex * 2 + 1] as node, searchDepth - 1, goodPyramidIndex * 2 + 1);
					expand_bottom_of_pyramid_and_traverse(goodHalfOfPyramid[goodPyramidIndex * 2 + 2] as node, searchDepth - 1, goodPyramidIndex * 2 + 2);
				}
			}
		}
		
		public function heuristic_cost(testNode:node):Number {
			//implement a heuristic that calculates potential cost (higher numbers are worse)
			var gameStateEdgeList:Array = new Array();
			gameStateEdgeList = gameStateEdgeList.concat((testNode.getGameState().edges));
			var returnValue = 0;
			var sumXs = 0;
			var numXs:int = 0;
			var aveX = 0;
			var sumYs = 0;
			var numYs:int = 0;
			var aveY = 0;
			var weightX = .01;
			for (var i = 0; i < gameStateEdgeList.length; i++) {
				var testEdge:edge = gameStateEdgeList[i] as edge;
				var touches = testEdge.getTimesTouched();
				if (touches == 0) {
					//if (testEdge.edgeStart.x >= testNode.getGameState().gameCircle.GetPosition().x || testEdge.edgeStart.y >= testNode.getGameState().gameCircle.GetPosition().y) {
						returnValue++;
						sumXs += testEdge.edgeStart.x;
						numXs++;
						sumYs += testEdge.edgeStart.y;
						numYs++;
					//}
				}
				else if (touches >= 2) {
					returnValue += 5;
				}
			}
			if (numXs != 0) {
				aveX = sumXs / numXs;
				//trace("Ave: " + aveX);
				//trace("Ball: " + testNode.getGameState().getPositionX());
				returnValue += Math.floor(Math.abs(aveX - testNode.getGameState().getPositionX()) * 10);
				//aveY = sumYs / numYs;
				//returnValue += Math.floor(Math.abs(aveY - testNode.getGameState().getPositionY()) * .1);
			}
			else {
				returnValue = -999999999;
				return returnValue;
			}
			if (testNode.getGameState().gameCircle.GetContactList() == null) {
				if (testNode.getActionTaken() == -100) {
					if (testNode.getGameState().getAngularVelocity() == 0.0) {
						returnValue += -1;
					}
					else {
						returnValue += 1;
					}
				}
				else if (testNode.getActionTaken() == 1) { 
					if (testNode.getGameState().getAngularVelocity() > 0.0) {
						returnValue += -1;
					}
					else {
						returnValue += 1;
					}
				}
				else if (testNode.getActionTaken() == 2) {
					if (testNode.getGameState().getAngularVelocity() < 0.0) {
						returnValue += -1;
					}
					else {
						returnValue += 1;
					}
				}
			}
			trace("Return: " + returnValue);
			return returnValue;
		}
		
		public function reconstruct_path(came_from:Dictionary, testNode:node):Array {
			if (came_from[testNode] != null) {
				var p:Array = new Array();
				p = p.concat((reconstruct_path(came_from, came_from[testNode])));
				p.push(testNode);
				return p;
			} else {
				var returnArray:Array = new Array();
				returnArray.push(testNode);
				return returnArray;
			}
		}
		
		public function generateNeighbors(inputNode:node):Array {
			var returnArray:Array = new Array();
			
			var returnGameState2:gamestate = set_and_step_offline_world(inputNode.getGameState(), true, 15);
			var returnNode2:node = new node(returnGameState2, 1);
			returnNode2.setActionTaken(2);
			
			returnArray.push(returnNode2);
			
			var returnGameState:gamestate = set_and_step_offline_world(inputNode.getGameState(), false, 15);
			var returnNode:node = new node(returnGameState, 1);
			returnNode.setActionTaken(1);
			
			returnArray.push(returnNode);
			
			
			
			return returnArray;
		}
		
		public function removeNulls(inputArray:Array):Array {
			var outputArray:Array = new Array();
			var referenceArray:Array = new Array();
			referenceArray = referenceArray.concat(inputArray);
			for (var i = 0; i < referenceArray.length; i++ ){
				if (referenceArray[i] == null) {
					var preorderArray:Array = new Array();
					for (var j = 0; j < i; j++) {
						preorderArray[j] = referenceArray[j];
					}
					var shiftedArray:Array = new Array();
					shiftedArray = shiftedArray.concat((copyArray(referenceArray, i, referenceArray.length)));
					shiftedArray.shift();
					if (shiftedArray == null) {
						break;
					}
					for (i = 0; i < shiftedArray.length; i++) {
						preorderArray.push(shiftedArray[i]);
					}
					referenceArray = new Array();
					referenceArray = referenceArray.concat(preorderArray);
				}
				outputArray[i] = referenceArray[i];
			}
			if (outputArray[0] == undefined) {
				outputArray = new Array();
				return outputArray;
			}
			return outputArray;
		}
		
		public function copyArray(inputArray:Array, startIndex:Number, endIndex:Number):Array {
			if (startIndex > endIndex) {
				throw new Error("endIndex was greater than startIndex!");
			}
			var outputArray:Array = new Array();
			var j:Number = 0;
			for (var i = startIndex; i < endIndex; i++) {
				outputArray[j] = inputArray[i];
				j++;
			}
			return outputArray;
		}
	}
}
